Halftoning is well known in the art. Image capture devices, such as cameras and scanners, typically record images using a range of tonal values for each pixel, such as, for example, 256 possible levels for each primary color. Since many printing processes utilize fixed-size dots of colorants to form images, halftoning is used to spatially distribute the dots in a manner which the eye interprets as having the appropriate overall tone.
In inkjet printing systems, an inkjet printhead is typically mounted on a carriage that is moved back and forth across a print media, such as paper. As the printhead is moved across the print media, a control system activates the printhead to deposit or eject fixed-size ink droplets onto the print media to form text and images. Ink is provided to the printhead from ink supplies that are either carried by the carriage or mounted to a fixed receiving station. Typically, at least four separate ink colors (such as black, cyan, magenta, and yellow) are required to faithfully reproduce color images.
In electrophotographic or “laser” printing systems, marking material commonly called “toner” is provided by an electrophotographic engine frequently referred to as a toner cartridge. The toner cartridge often includes an intermediate imaging device such as a drum, and a reservoir of imaging material such as powdered toner. The drum is charged using an energy source such as a scanning laser. The process is substantially binary, in that a small region forming a dot is either “on” or “off”. The imaging material is attracted to the charged drum and is then transferred to print media.
One common halftoning technique is known as error diffusion. In error diffusion, for each color component of an image pixel, the decision to output a corresponding output pixel by the image-forming device is based on the intensity level of the color component of the image pixel, as well as the output pixels output for the previous image pixels. Error diffusion tries to distribute output pixels so as to reduce or eliminate pixel overlap, reduce large areas of empty space between output pixels, and otherwise create eye-pleasing patterns. For a more complete discussion of error diffusion halftoning, see Robert Ulichney, Digital Halftoning, MIT Press, Cambridge, Mass., 1987.
Halftoning is typically computationally intensive, in that each pixel of the image must be sequentially processed; further, many halftoning techniques require multiple iterations. Many techniques function well in some circumstances but produce visible artifacts in other situations, such as when two or more color components of comparable strength form part of an image. Other factors also affect perceived image quality; for example, for best image quality, it is typically desirable that the printing of multiple colorants on the same dot be minimized. Managing the distribution of overall dots and individual color dots homogeneously while maintaining minimum dot-on-dot printing has proven to be a very hard problem to solve, especially with efficient, non-iterative halftoning methods such as error diffusion. There is thus a continuing need for halftoning techniques that are computationally efficient yet produce images with a minimum of perceptible artifacts.